\graphicspath{{./figures/algorithms/}}

\chapter{Algoritmos Propuestos}
\label{chap:algorithms}

% %\clearpage
\section{Introducción}
\label{sec:introalgorithms}


El estudio reportado en el Capítulo \ref{cap:experimentos} demostró que para lograr una convergencia robusta es indispensable contar con un esquema de jerarquización que provea una fuerte presión de selección mediante una discriminación estricta entre soluciones. Sin embargo, también se observó que una presión de selección elevada tiende a sacrificar la  diversidad y por lo general se converge hacia un único punto de la superficie compromiso. Este problema, conocido como deriva genética (ver Sección \ref{sec:conclusionfitness}), puede evitarse mediante la incorporación de mecanismos para promover diversidad en la población.  

Al igual que la convergencia, la diversidad es un requerimiento cuando se optimizan múltiples objetivos; sin embargo, estos requerimientos están en conflicto y la mejor diversidad esta comúnmente asociada con una convergencia pobre \cite{Purshouse07}. Por lo tanto, la preservación de diversidad debe hacerse de un modo tal que no afecte negativamente la convergencia.

Generalmente la diversidad se promueve como criterio secundario para discriminar entre soluciones que comparten la misma jerarquía. No obstante, cuando se tiene una máxima discriminación de soluciones, dado que cada solución tendría por lo regular una jerarquía diferente, utilizar mecanismos de promoción de diversidad como criterio secundario claramente no tendría ningún efecto, por lo que resulta necesario desarrollar enfoques con una metodología más adecuada para solventar este tipo de escenarios. 

En este capítulo proponemos dos nuevos MOEAs cuya característica principal es que mantienen como prioridad el requerimiento de convergencia al mismo tiempo que incorporan mecanismos para preservar la existencia de diversidad en la población. Para la validación estadística de estas propuestas seleccionamos un conjunto de MOEAs representativos del estado del arte y realizamos un estudio comparativo. Los resultados de dicho estudio demuestran que los algoritmos propuestos son significativamente superiores a los enfoques tomados de la literatura, al menos para los experimentos realizados.

% En estos casos, donde muchos objetivos requieren ser optimizados, el conflicto entre los requerimientos de convergencia y diversidad se hace más evidente \cite{Purshouse07}: El volumen del espacio de objetivos se incrementa exponencialmente al incrementarse linealmente el número de objetivos. Para una población finita de soluciones, ésto provee mayor oportunidad de que una determinada solución sea remota al resto de las soluciones, distante de la superficie compromiso, y aún ser localmente no dominada. Bajo estas circunstancias, los mecanismos de preservación de diversidad tienden a preferir soluciones con una convergencia pobre, dirigiendo la búsqueda lejos de la superficie compromiso.


\section{Algoritmo base}
\label{sec:algoritmobase}

Los dos enfoques propuestos se han implementado sobre un algoritmo base cuyo flujo de ejecución se describe mediante la figura \ref{fig:baseflow}.
\begin{figure}[htp] 
\centering
\shadowbox{\includegraphics[width=9.5cm]{algoritmobase.pdf}}
\caption{Algoritmo base: Flujo de ejecución.}
\label{fig:baseflow}
\end{figure}
Inicialmente se genera de manera aleatoria una población de $N$ padres. Sobre esta población se realiza un proceso de selección para identificar los padres que podrán reproducirse. Con los padres seleccionados se aplican los operadores de variación (cruza y mutación) para generar una población de $N$ hijos.  La población de padres y la nueva población de hijos son ahora combinadas, lo que da como resultado una población de tamaño $2N$, de donde serán seleccionados los $N$ individuos que formarán la población de padres para la siguiente generación (MOEA elitista \cite{Deb00}). Este proceso se repite durante un número determinado de generaciones.

Los operadores implementados son: selección por torneo binario (\textit{binary tournament selection}) basada en la jerarquía (aptitud) de las soluciones. Cruza binaria simulada (\textit{simulated binary crossover}, SBX)  ($\eta_{c} = 15$) con probabilidad de 1.0 \cite{Deb95}. Mutación polinomial (\textit{polynomial mutation}) ($\eta_{m} = 20$) con probabilidad de 1/$n$, donde $n$ es el número de variables de decisión  \cite{Deb96}.

% % Componentes y parámetros
% El MOEA implementado utiliza selección mediante torneo binario (binary tournament selection) basada en la jerarquía (aptitud) de las soluciones. Como operadores de variación, este MOEA incorpora la cruza binaria simulada (simulated binary crossover, SBX) ($\eta_{c} = 15$) \cite{Deb95} y mutación polinomial (polynomial mutation) ($\eta_{c} = 20$) \cite{Deb96}, con probabilidades de 1.0 y 1/$n$ respectivamente, donde $n$ es el número de variables de decisión. Para todos los experimentos reportados en esta sección se utilizó una población de $N=100$ individuos y 300 generaciones para la búsqueda. Con el propósito de evitar alteraciones en el comportamiento de los métodos estudiados, el MOEA implementado no incorpora ningún mecanismo adicional para preservar diversidad en la población.

\section{Algoritmo genético elitista basado en agrupamiento}
\label{sec:cega}

El agrupamiento (o \textit{clustering} como es más comúnmente conocido\footnote{En esta tesis se utilizaran indistintamente los términos agrupamiento y \textit{clustering}.}) permite la clasificación de una colección de elementos con base en sus similitudes. El algoritmo genético elitista basado en \textit{clustering} (\textit{clustering-based elitist genetic algorithm}, o $\mathbf{CEGA^*}$ por brevedad) es un MOEA que incorpora \textit{clustering} como mecanismo para preservación de diversidad\footnote{La idea de utilizar \textit{clustering} para promover diversidad en MOEAs no es nueva (ver por ejemplo \cite{Zitzler99c,Molyneaux01}).}, al mismo tiempo que utiliza una estrategia de jerarquización estricta para promover la convergencia. 

$\mathbf{CEGA^*}$ se implementó sobre el algoritmo base descrito en la Sección \ref{sec:algoritmobase}. El flujo básico de ejecución del algoritmo resultante se muestra en la figura \ref{fig:cegaflow}. 
\begin{figure}[htp] 
\centering
\shadowbox{\includegraphics[width=11cm]{cega.pdf}}
\caption{$\mathbf{CEGA^*}$: Flujo de ejecución.}
\label{fig:cegaflow}
\end{figure}
En la figura \ref{fig:cegaflow} se encuentran resaltados mediante recuadros punteados los elementos clave de $\mathbf{CEGA^*}$. Por un lado, un mecanismo de jerarquización que será utilizado para asignar a los individuos un valor (aptitud) para competir durante el proceso de selección. Por otro lado, una estrategia basada en \textit{clustering} que en conjunción con el mecanismo de jerarquización permitirá la selección de los $N$ individuos que sobrevivirán y formarán la población de padres para la siguiente generación. Estos elementos serán descritos por separado a continuación.

\subsection{Jerarquización}
\label{sec:jerarquizacion}

$\mathbf{CEGA^*}$ incorpora el método  $\mathbf{GDET^*}$ descrito en la Sección \ref{sec:proposedfrd} como mecanismo discriminante. $\mathbf{GDET^*}$ consiste en penalizar a cada individuo, por la magnitud de la diferencia con que es superado al compararse, objetivo por objetivo, con respecto al resto de la población. De acuerdo con este método la aptitud de un determinado individuo $\mathbf{X}_{i}$ se calcula de la siguiente manera:
\begin{eqnarray} 
 \mathbf{GDET^*}(\mathbf{X}_{i}) & = & \sum_{\mathbf{X}_{j} \neq \mathbf{X}_{i}} \sum_{m=1}^{M} \max(f_{m}(\mathbf{X}_{i}) - f_{m}(\mathbf{X}_{j}), 0)
\end{eqnarray}	
$\mathbf{GDET^*}$ es un criterio de minimización, por lo que se dice que un individuo $\mathbf{X}_{i}$ domina a otro individuo $\mathbf{X}_{j}$ si y sólo si   $\mathbf{GDET^*}(\mathbf{X}_{i}) <  \mathbf{GDET^*}(\mathbf{X}_{i})$. Consultar Sección \ref{sec:proposedfrd} para mayores detalles de este método.


\subsection{Proceso de agrupamiento}
\label{sec:clusteringstep}


El algoritmo de \textit{clustering} implementado para $\mathbf{CEGA^*}$ sigue un enfoque \textit{jerárquico aglomerativo} (ver figura \ref{fig:clusteringjerarquico}). Inicialmente cada individuo de la población representa un \textit{cluster} diferente y de manera iterativa se combinan los dos \textit{clusters} más similares hasta completar la cantidad deseada de grupos. 
\begin{figure}[htp] 
\centering
\shadowbox{\includegraphics[width=7cm]{clustering.pdf}}
\caption{Agrupamiento (\textit{Clustering}) jerárquico aglomerativo.}
\label{fig:clusteringjerarquico}
\end{figure}

El algoritmo de \textit{clustering} se aplicará en el espacio de las variables de decisión. El propósito de utilizar \textit{clustering} es asistir en la selección de los individuos mejor distribuidos en el espacio de las variables de decisión, de esta manera promover la diversidad en la población y, por lo tanto, favorecer la capacidad exploratoria del algoritmo. Como medida de similitud entre \textit{clusters} se utilizará la distancia promedio (\textit{average linkage}): la distancia entre dos \textit{clusters} $c_1$ y $c_2$ es el promedio de las distancias entre cada pareja de soluciones $\mathbf{X}_{i}$ y $\mathbf{X}_{j}$ tales que $\mathbf{X}_{i}\in c_1$ y $\mathbf{X}_{j} \in c_2$\footnote{En este trabajo se usó la distancia Euclidiana para calcular la cercanía entre un par de soluciones.}.  El algoritmo de \textit{clustering} se aplicará sobre los $2N$ individuos que forman la unión de las poblaciones de padres e hijos (ver figura \ref{fig:cegaflow}). Se seleccionarán $N$ individuos para formar la población de padres de la siguiente generación, de tal manera que la cantidad de \textit{clusters} necesaria para este enfoque se encuentra en el rango $[2, N]$. Todos nuestros experimentos involucran una población de $N=100$ individuos y, por razones que se discutirán posteriormente en la Sección \ref{sec:justificacioncega}, para este trabajo se utilizarán un total de $C=N/2=50$ \textit{clusters}.


 
\subsection{Estrategia de selección}
\label{sec:estrategiaseleccion}

Esta etapa consiste en seleccionar $N$ de los $2N$ individuos en la población combinada de padres e hijos para que sobrevivan y formen la población de padres de la siguiente generación. Este proceso de selección se realizará de la siguiente manera:

% Los criterios utilizados para este proceso de selección son los siguientes:

% Esta etapa consiste en seleccionar los N individuos con las mejores características que sobrevivirán y formarán la población de padres para la siguiente generación a partir de los $2N$ individuos de la población combinada de padres e hijos. Los criterios utilizados para este proceso de selección son los siguientes:
% Los criterios utilizados para este proceso de selección se describen mediante el Algoritmo \ref{alg:cegaselection}.

\begin{enumerate}
\item \label{step:ranking} Calcular la aptitud de cada individuo en la población combinada utilizando el método $\mathbf{GDET^*}$ descrito en la Sección \ref{sec:jerarquizacion}.
\item Generar $C$ \textit{clusters} sobre los $2N$ individuos en la población combinada de la forma descrita en la Sección \ref{sec:clusteringstep}.
\item \label{step:clusterselection}Seleccionar el mejor representante de cada uno de los $C$ \textit{clusters}. Para este propósito se jerarquizan de manera local los individuos dentro de un mismo \textit{cluster} de acuerdo con el método $\mathbf{GBST^*}$ descrito en la Sección \ref{sec:proposedfrd} (ver figura \ref{fig:localgbst}). Si se presenta el caso en que haya más de un individuo en el mismo \textit{cluster} con la mejor aptitud de acuerdo al método $\mathbf{GBST^*}$, se elegirá uno de manera aleatoria.
\begin{figure}[htp] 
\centering
\shadowbox{\includegraphics[width=7cm]{localgbst.pdf}}
\caption{$\mathbf{GBST^*}$ aplicado localmente para elegir el individuo representante de cada \textit{cluster}.}
\label{fig:localgbst}
\end{figure}

\item En el paso \ref{step:clusterselection} se seleccionaron $C$ individuos. En caso de que $C<N$, seleccionar los $N-C$ individuos restantes considerando únicamente su jerarquía global obtenida con $\mathbf{GDET^*}$ en el paso \ref{step:ranking} (omitiendo los individuos ya seleccionados previamente).
\end{enumerate}

% \begin{algorithm}[htbp]
% \begin{algorithmic}[1]
% 	\STATE  Calcular la aptitud de cada individuo en la población combinada $R_{gen}$ utilizando el método GDET descrito en la Sección \ref{sec:jerarquizacion}.
% 	\STATE	Generar $C$ \textit{clusters} sobre $R_{gen}$ de la forma descrita en la Sección \ref{sec:clusteringstep}.
% 	\STATE \label{step:clusterselection}Seleccionar el mejor representante de cada uno de los $C$ \textit{clusters}. Para este propósito se jerarquizan de manera local los individuos dentro de un mismo \textit{cluster} de acuerdo con el método GBST descrito en la Sección \ref{sec:proposedfrd}. Si se presenta el caso en que más de un individuo en el mismo \textit{cluster} tiene la mejor aptitud para el método GBST, se elegirá de manera aleatoria.
% 	\STATE Con el paso \ref{step:clusterselection} se seleccionaron $C$ individuos. En caso de que $C<$ N, seleccionar los N$-C$ individuos restantes considerando únicamente su jerarquía global obtenida con GDET y omitiendo los individuos ya seleccionados previamente.
% \end{algorithmic}
% \caption{$\mathbf{CEGA^*}$: Estrategia de selección.}
% \label{alg:cegaselection}
% \end{algorithm}

De esta manera, la estrategia de selección propuesta mantiene como prioridad la convergencia al mismo tiempo que promueve la existencia de diversidad en la población.



\subsection{Justificación de ajuste de parámetros y operadores}
\label{sec:justificacioncega}


El desempeño de $\mathbf{CEGA^*}$ depende de distintos factores:

\begin{enumerate}
\item Estrategia utilizada ($E$): se implementaron 14 estrategias diferentes para el algoritmo, $E=\{$CEGA1, CEGA2, $\dots$, CEGA14$\}$. Estas alternativas a grandes rasgos difieren en la forma de utilizar la jerarquización y el procedimiento de \textit{clustering} para guiar el proceso de búsqueda.

\item Medida de similitud entre \textit{clusters} ($S$): Se implementaron tres enfoques para caracterizar la similitud de un par de \textit{clusters} ($|S|=3$): distancia promedio (\textit{average linkage}), mínima distancia (\textit{single linkage}) y máxima distancia (\textit{complete linkage}).

\item Número de \textit{clusters} ($C$): Tal como se mencionó en la Sección \ref{sec:clusteringstep}, el número de \textit{clusters} posibles para nuestro enfoque se encuentra en el rango $[2, N]$. Sin embargo, fue necesario discretizar este rango y, dado que para nuestra experimentación utilizamos una población de tamaño $N$=100, los valores considerados para este parámetro son $C=\{25, 50, 75\}$.

\item Método de asignación de aptitud ($A$): Distintos de nuestros métodos propuestos en el Capítulo \ref{chap:proposed} demostraron proveer buena capacidad de convergencia para la experimentación reportada en el Capítulo \ref{cap:experimentos}. Una vez más fue necesario discretizar nuestras opciones y decidimos experimentar con $A=\{\mathbf{PRFT^*}, \mathbf{GBST^*}, \mathbf{GDET^*}\}$.
\end{enumerate}

Los diferentes ajustes de parámetros descritos anteriormente generan un total de $|E|\times|S|\times|C|\times|A|=14\times3\times3\times3=378$ configuraciones posibles para el algoritmo. Las distintas configuraciones proveen comportamientos muy diferentes para $\mathbf{CEGA^*}$, de tal forma, se tomó la decisión de verificar estadísticamente cada una de estas alternativas para seleccionar las características que permitieran un mejor desempeño. De esta manera, las 378 configuraciones de $\mathbf{CEGA^*}$ fueron evaluadas para los seis problemas de prueba descritos en la Sección \ref{sec:dtlz}, utilizando instancias de $M=\{5, 10, 15, 20, 30, 50\}$ objetivos y con 31 repeticiones independientes para cada experimento. Por motivos de espacio los resultados de esta extensa experimentación no son mostrados en este documento. Sin embargo, la descripción presentada previamente para $\mathbf{CEGA^*}$ corresponde a la configuración más prometedora de acuerdo con los resultados obtenidos.




\section{Asignación de aptitud en direcciones múltiples}
\label{sec:mvfa}

% Para establecer diferentes direcciones de búsqueda se utiliza un conjunto de vectores de pesos.

La estrategia de asignación de aptitud en direcciones múltiples (\textit{Multi-Directional Fitness Asignment}, $\mathbf{MDFA^*}$), es un mecanismo de asignación de aptitud para guiar el proceso de búsqueda en diferentes direcciones simultáneamente. Para establecer diferentes direcciones de búsqueda se utiliza un conjunto de vectores de pesos. Un vector de pesos es un conjunto de valores o coeficientes que denotan la importancia relativa de cada uno de los objetivos. De este modo, asumimos que diferentes vectores de pesos permitirían dirigir la búsqueda hacia diferentes regiones del espacio de objetivos\footnote{El uso de múltiples vectores de pesos para asignar aptitud a un conjunto de soluciones no es una idea nueva, tal es el caso del algoritmo $\mathbf{MSOPS}$ \cite{Hughes03b} que se describe más adelante en la Sección \ref{sec:msops}.}.

$\mathbf{MDFA^*}$ se implementó utilizando como base el algoritmo descrito en la Sección \ref{sec:algoritmobase}. La figura \ref{fig:mdfaflow} describe el flujo de ejecución del MOEA resultante. 
\begin{figure}[h] 
\centering
\shadowbox{\includegraphics[width=11cm]{mdfa.pdf}}
\caption{$\mathbf{MDFA^*}$: Flujo de ejecución.}
\label{fig:mdfaflow}
\end{figure}
El proceso de jerarquización es específicamente nuestra propuesta (este elemento ha sido resaltado con un rectángulo punteado en la figura \ref{fig:mdfaflow}) y será descrito a continuación.

\subsection{Jerarquización $\mathbf{MDFA^*}$}


La jerarquización se realiza con un doble propósito: por un lado, asignar a cada individuo un valor con el que competirá al momento de seleccionar los que podrán reproducirse. Por otro lado, discriminar entre individuos al momento de seleccionar los que sobrevivirán y formarán la población de padres para la siguiente generación. Considerando una población de tamaño $N$, el proceso de jerarquización $\mathbf{MDFA^*}$  requiere la especificación de un conjunto $V$ con $N$ vectores de pesos diferentes ($|V|=N$).  

El proceso de jerarquización $\mathbf{MDFA^*}$ se describe mediante el Algoritmo \ref{alg:mdfa}. 
\begin{algorithm}[h]
\begin{algorithmic}[1]
\REQUIRE MDFA()
	\STATE $aptitud[\mathbf{X}_i] \leftarrow \infty \;\;\; \forall{\mathbf{X}_{i} \in P}$ 
	\STATE \textbf{- Etapa 1:}
	\FORALL{$v \in V$} 
	 	\STATE	Encontrar $\mathbf{X}_{i} \in P : \mathbf{WSUM}(\mathbf{X}_{i}, v) < \mathbf{WSUM}(\mathbf{X}_{j}, v) \;\;\; \forall{\mathbf{X}_{j} \in P}: \mathbf{X}_{j} \neq \mathbf{X}_{i}$
		\IF{$\mathbf{WSUM}(\mathbf{X}_{i}, v) < aptitud[\mathbf{X}_i] $} 
			\STATE $aptitud[\mathbf{X}_i] \leftarrow \mathbf{WSUM}(\mathbf{X}_{i}, v)$
		\ENDIF
	\ENDFOR

	\STATE \textbf{- Etapa 2:}

	\STATE $peor\_etapa1 \leftarrow \displaystyle \max(aptitud[\mathbf{X}_i]) \;\;\; \forall{\mathbf{X}_{i} \in P : aptitud[\mathbf{X}_i] \neq \infty}$

	\FORALL{$\mathbf{X}_{i} \in P : aptitud[\mathbf{X}_i] = \infty$} 
	 	\STATE $aptitud[\mathbf{X}_i] \leftarrow \displaystyle \max_{v \in V}(\mathbf{WSUM}(\mathbf{X}_{i}, v)) + peor\_etapa1$
	\ENDFOR	
\ENSURE 
\REQUIRE $\mathbf{WSUM}$($\mathbf{X}_i$, $v$)
	\RETURN $\displaystyle \sum_{m=1}^{M}{ v_mf_m(\mathbf{X}_i)}$ 
\ENSURE 
\end{algorithmic}
\caption{Asignación de aptitud $\mathbf{MDFA^*}$.}
\label{alg:mdfa}
\end{algorithm}
Todos los individuos se evalúan para cada uno de los vectores de pesos utilizando algún enfoque de agregación. En este trabajo se implementó la suma ponderada ($\mathbf{WSUM}$, ver Sección \ref{subsec:sinparametros}). Para cada vector de pesos se identifica el individuo con el mejor desempeño. Si un individuo fue identificado por tener el mejor desempeño para alguno de los vectores, asignar este desempeño como aptitud para dicho individuo. Dado que un mismo individuo puede ser el mejor para varios vectores de pesos, su aptitud será la mejor de todas las obtenidas con ese conjunto de vectores. Los individuos a los que no se les asignó aptitud (puesto que no mostraron el desempeño más alto para ningún vector), recibirán como aptitud el peor desempeño que obtuvieron para los diferentes vectores. Adicionalmente, la aptitud de estos individuos será penalizada sumándole la peor de las aptitudes asignadas en la primera etapa. Al asignar a estos individuos la peor de sus aptitudes se dará preferencia a los individuos con un mejor desempeño promedio. Penalizarlos con la peor aptitud de la primer etapa permitirá asegurar que estos tendrán menor preferencia (son inferiores) que el primer conjunto de individuos.

De esta manera, $\mathbf{MDFA^*}$ mantiene como prioridad el requerimiento de convergencia, al mismo tiempo que promueve dirigir la búsqueda en diferentes direcciones simultáneamente y preserva diversidad en la población.

\subsection{Justificación de ajuste de parámetros y operadores}
\label{sec:justificacionmdfa}

Los factores que pueden afectar el comportamiento de $\mathbf{MDFA^*}$ se listan a continuación:
\begin{enumerate}
 \item Estrategia utilizada, $E$: Se implementaron 5 estrategias diferentes para este enfoque, $E=\{$MDFA1, MDFA2,  \dots, MDFA5$\}$. Estas estrategias difieren principalmente en la forma de utilizar el conjunto de vectores de pesos para asignar la aptitud de los individuos y qué hacer con los individuos que no recibieron aptitud a través de este proceso.
\item Conjunto de vectores de pesos, $VS$: Se experimentó con conjuntos vectores de pesos generados de 3 formas distintas, $VS=\{VS1, VS2, VS3\}$:
\begin{enumerate}
\item $VS1$: Vectores de pesos generados con una herramienta desarrollada por Hughes para su algoritmo $\mathbf{MSOPS}$ \cite{Hughes03b},  disponible para uso académico en \cite{hughescodes}. 
\item $VS2$: Vectores de pesos generados aleatoriamente en el rango $[0.5, 1]$.
\item $VS3$: Vectores de pesos generados aleatoriamente en el rango $[0.25, 1]$.
\end{enumerate}
\end{enumerate}


Estos factores generan un total de $|E|\times|VS|=5\times3=15$ configuraciones para $\mathbf{MDFA^*}$. Del mismo modo que con $\mathbf{CEGA^*}$, evaluamos estas 15 configuraciones utilizando los seis problemas de prueba adoptados, con $M=\{5, 10, 15, 20, 30, 50\}$ objetivos y considerando 31 repeticiones independientes para cada experimento. El procedimiento de jerarquización $\mathbf{MDFA^*}$ detallado anteriormente corresponde a la estrategia que mostró el mejor desempeño de acuerdo con las estadísticas obtenidas con esta experimentación. El conjunto de vectores de pesos que aportó el mejor comportamiento para el algoritmo es $VS3$, es decir, vectores de pesos generados aleatoriamente en el rango $[0.25, 1]$.


\section{Experimentación}
\label{sec:algorithmsexperimentation}

El propósito de esta fase de experimentación es estudiar el comportamiento de los algoritmos propuestos en términos de convergencia y diversidad, así como también la escalabilidad de estos enfoques con respecto al número de objetivos. Para esta experimentación se consideraron los diferentes problemas de prueba descritos en la Sección \ref{sec:dtlz}, utilizando instancias de tamaño $M=\{5, 10, 15, 20, 30, 50\}$, donde $M$ denota el número de objetivos a optimizar.

Para estos experimentos hemos incluido como punto de referencia y comparación 4 MOEAs tomados de la literatura especializada. Algunos de estos MOEAs han sido propuestos específicamente para lidiar con el aumento en el número de objetivos, mientras que otros son optimizadores multiobjetivo representativos que han sido ampliamente utilizados en estudios comparativos. Tanto nuestros algoritmos como los de la literatura han sido evaluados utilizando una población de $N=100$ individuos durante 300 generaciones.

En la Sección \ref{sec:stateofartalgorithms} se describen de manera introductoria los diferentes enfoques de la literatura considerados. Finalmente, la Sección \ref{sec:resultadosalgorithms} presenta los resultados obtenidos con esta experimentación.


\subsection{Algoritmos del estado del arte tomados para realizar la comparativa}
\label{sec:stateofartalgorithms}

\subsubsection{$\mathbf{NSGA}$-$\mathbf{II}$}
\label{sec:nsga2}

El \textit{Elitist Non-Dominated Sorting Genetic Algorithm} ($\mathbf{NSGA}$-$\mathbf{II}$), propuesto por Deb \textit{et al.} en 2000 \cite{Deb00f,Deb02}, se ha convertido en el MOEA más representativo de la literatura y ha sido utilizado ampliamente como punto de referencia para comparativas en nuevos desarrollos. Por esta razón, y aunque se ha demostrado que este algoritmo no trabaja bien al incrementarse la cantidad de objetivos \cite{Purshouse03b,Khare03,Ishibuchi08e}, hemos considerado a $\mathbf{NSGA}$-$\mathbf{II}$ para este estudio comparativo. $\mathbf{NSGA}$-$\mathbf{II}$ implementa el \textit{Non-Dominated Sorting} (NDS), que es un método de jerarquización basado en la relación de dominancia de Pareto (ver Sección \ref{sec:paretobased}) y fue propuesto originalmente por Goldberg en 1989 \cite{Goldberg89}. Una de las características principales de $\mathbf{NSGA}$-$\mathbf{II}$ es la incorporación de un mecanismo explícito para preservación de diversidad, al que los autores nombraron \textit{crowding distance} (CWD). CWD estima la densidad de la región del espacio de objetivos donde se encuentra cada solución. Este operador se utiliza como criterio secundario para discriminar entre soluciones con la misma jerarquía, dando preferencia a aquellas ubicadas en regiones menos densas. El Algoritmo \ref{alg:nsga2} describe el flujo de ejecución de $\mathbf{NSGA}$-$\mathbf{II}$. Para mayor detalles del algoritmo referirse a \cite{Deb00f,Deb02}.


\begin{algorithm}[htbp]
\begin{algorithmic}[1]
	\STATE  $gen \leftarrow 0$
	\STATE	Generar aleatoriamente población inicial de $N$ padres: $P_{gen}$
	\STATE Jerarquizar $P_{gen}$ usando \textit{Non-Dominated Sorting} (ver Sección \ref{sec:paretobased}): NDS($P_{gen}$)
	\WHILE{$gen < GMAX$ (repetir durante $GMAX$ generaciones)}
		\STATE Torneo binario basado en la jerarquía de las soluciones. Si dos soluciones tienen la misma jerarquía, utilizar CWD como criterio de preferencia. 
		\STATE Aplicar cruza y mutación para generar la población de $N$ hijos: $Q_{gen}$
		\STATE Combinar poblaciones de padres e hijos: $R_{gen} \leftarrow P_{gen}\cup Q_{gen}$ ($|R_{gen}| = 2N$)
		\STATE Jerarquizar $R_{gen}$ usando \textit{Non-Dominated Sorting} (ver Sección \ref{sec:paretobased}): NDS($R_{gen}$)
		\STATE Seleccionar $N$ individuos de $R_{gen}$ (con respecto a la jerarquía) para formar la población de padres para la siguiente generación, $P_{gen+1}$. Si existen más soluciones con la misma jerarquía que la capacidad disponible en $P_{gen+1}$, seleccionar sólo $N-|P_{gen+1}|$ individuos utilizando CWD como criterio de discriminación.
		\STATE $gen \leftarrow gen + 1$
	\ENDWHILE
\end{algorithmic}
\caption{$\mathbf{NSGA}$-$\mathbf{II}$: Flujo de ejecución.}
\label{alg:nsga2}
\end{algorithm}




\subsubsection{$\mathbf{DMO}$}

Adra y Fleming \cite{Adra09} propusieron en 2009 un operador para administrar el uso de mecanismos de preservación de diversidad dentro de un MOEA. Los autores nombraron a este operador \textit{Diversity Management Operator} ($\mathbf{DMO}$) y lo presentaron como una alternativa para promover diversidad en problemas donde muchos (más de tres) objetivos requieren ser optimizados. $\mathbf{DMO}$ es una estrategia adaptativa: los mecanismos de preservación de diversidad son activados únicamente cuando las condiciones de la población así lo requieran. Para conocer el estado de la población (con respecto a la diversidad) en determinada etapa de la búsqueda, $\mathbf{DMO}$ utiliza la métrica de \textit{máxima extensión} (\textit{máximum spread}) propuesta por Zitzler en \cite{zitz1999a}. Esta métrica se define mediante la siguiente ecuación:
\begin{eqnarray}
\label{eq:maxspread}
D & = & \sqrt{ \sum_{m=1}^{M}{\left( \displaystyle \max_{\mathbf{X}_{i} \in Z}{\{f_{m}(\mathbf{X}_{i})\}} - \min_{\mathbf{X}_{i} \in Z}{\{f_{m}(\mathbf{X}_{i})\}}  \right)^2 }}
\end{eqnarray}
donde $D$ corresponde a la medida de la diagonal del hipercubo formado por los extremos de $Z$, que representa el subconjunto de soluciones no dominadas (con respecto a la dominancia de Pareto) en la población actual. De este modo, $D$ usa la máxima extensión en cada dimensión del espacio de objetivos para estimar el rango en que las soluciones de $Z$  se encuentran distribuidas. Una vez que el indicador $D$ ha sido calculado, éste se normaliza con respecto a un valor óptimo para la métrica, $D^{*}$, sugerido por el tomador de decisiones. $D^{*}$ puede calcularse reemplazando $Z$ por $P^{*}$ en la ecuación (\ref{eq:maxspread}), donde  $P^{*}$ es un conjunto de referencia que representa el FP para el problema a optimizar. El indicador normalizado de diversidad, $I_{s}$, se define entonces de la siguiente manera:
\begin{eqnarray}
I_{s} & = &  D/D^{*}
\end{eqnarray}
$I_{s}$ puede tomar cualquier valor positivo, del que depende la activación o desactivación de los mecanismos de preservación de diversidad. Por un lado, $I_{s}=1-\varepsilon$ corresponde a una diversidad ideal y $I_{s}>1-\varepsilon$ indica una dispersión excesiva de las soluciones en el espacio de objetivos, situaciones en las que los autores proponen desactivar la promoción de diversidad. Por otro lado, $I_{s}<1-\varepsilon$ se interpreta como escasez de diversidad en la población, por lo que los mecanismos de diversidad son activados. $\varepsilon$ es un valor opcional de tolerancia, el cual ha sido omitido en este trabajo ($\varepsilon=0$). En \cite{Adra09} se propone la incorporación de $\mathbf{DMO}$ en el algoritmo $\mathbf{NSGA}$-$\mathbf{II}$ descrito en la Sección \ref{sec:nsga2}. El enfoque resultante de esta hibridación se describe en el Algoritmo \ref{alg:nsga2dmo}.


\begin{algorithm}[htbp]
\begin{algorithmic}[1]
	\STATE  $gen \leftarrow 0$
	\STATE	Generar aleatoriamente población inicial de $N$ padres: $P_{gen}$
	\STATE Jerarquizar $P_{gen}$ usando \textit{Non-Dominated Sorting} (ver Sección \ref{sec:paretobased}): NDS($P_{gen}$)
	\WHILE{$gen < GMAX$ (repetir durante GMAX generaciones)}
		\STATE $Z \leftarrow soluciones\_no\_dominadas(P_{gen})$
		\STATE $I_{s} \leftarrow diversidad\_normalizada(Z)$
		\STATE Torneo binario basado en la jerarquía de las soluciones. Cuando dos soluciones tienen la misma jerarquía: si $I_{s}<1-\varepsilon$ utilizar CWD como criterio de preferencia, de otro modo elegir aleatoriamente.
		\STATE Aplicar cruza y mutación para generar la población de hijos: $Q_{gen}$
		\STATE Combinar poblaciones de padres e hijos: $R_{gen} \leftarrow P_{gen}\cup Q_{gen}$ ($|R_{gen}| = 2N$)
		\STATE Jerarquizar $R_{gen}$ usando \textit{Non-Dominated Sorting} (ver Sección \ref{sec:paretobased}): NDS($R_{gen}$) 
		\STATE Seleccionar $N$ individuos de $R_{gen}$ (con respecto a la jerarquía) para formar la población de padres para la siguiente generación, $P_{gen+1}$. Si existen más soluciones con la misma jerarquía que la capacidad disponible en $P_{gen+1}$, seleccionar sólo $N-|P_{gen+1}|$ individuos utilizando CWD como criterio de discriminación si se cumple que $I_{s}<1-\varepsilon$, de otro modo hacerlo de manera aleatoria.
		\STATE $gen \leftarrow gen + 1$
	\ENDWHILE
\end{algorithmic}
\caption{$\mathbf{DMO}$ incorporado en $\mathbf{NSGA}$-$\mathbf{II}$: Flujo de ejecución.}
\label{alg:nsga2dmo}
\end{algorithm}



\subsubsection{$\mathbf{HypE}$}

Bader y Zitzler \cite{Bader08} propusieron $\mathbf{HypE}$ (\textit{Hypervolume Estimation Algorithm for Multiobjective Optimization}), un MOEA basado en la métrica de hipervolumen. La métrica de hipervolumen ha sido ampliamente utilizada para evaluar y comparar el desempeño de MOEAs. $\mathbf{HypE}$ implementa esta métrica como parte de su mecanismo de asignación de aptitud para guiar el proceso de búsqueda. La aptitud de una determinada solución $\mathbf{X}_{i}$ está dada por el hipervolumen que se atribuye a $\mathbf{X}_{i}$ con respecto al hipervolumen global de todo el conjunto de soluciones. Dado que el costo computacional requerido para calcular el hipervolumen se incrementa exponencialmente con el número de objetivos, $\mathbf{HypE}$ aproxima los valores de esta métrica mediante simulación de Monte Carlo. Para $\mathbf{HypE}$ no es tan importante el valor real de la métrica, sino la jerarquización que puede inducirse mediante este indicador sobre una población de soluciones candidatas. De esta manera, los autores presentan a $\mathbf{HypE}$ como una alternativa capaz de explotar las ventajas de este indicador y al mismo tiempo escalable con respecto al número de objetivos. El Algoritmo \ref{alg:hype} describe el flujo básico de ejecución de $\mathbf{HypE}$. Sin embargo, para profundizar en los detalles de la estimación del hipervolumen y el cálculo de la aptitud de las soluciones refiérase a \cite{Bader08}.

\begin{algorithm}[htbp]
\begin{algorithmic}[1]
	\STATE  $gen \leftarrow 0$
	\STATE	Generar aleatoriamente población inicial de $N$ padres: $P_{gen}$
	\STATE Jerarquizar $P_{gen}$ usando \textit{Non-Dominated Sorting} (ver Sección \ref{sec:paretobased}): NDS($P_{gen}$)
	\WHILE{$gen < GMAX$ (repetir durante GMAX generaciones)}
		\STATE Torneo binario basado en la contribución estimada de las soluciones para la métrica del hipervolumen.
		\STATE Aplicar cruza y mutación para generar la población de hijos: $Q_{gen}$
		\STATE Combinar poblaciones de padres e hijos: $R_{gen} \leftarrow P_{gen}\cup Q_{gen}$ ($|R_{gen}| = 2N$)
		\STATE Jerarquizar $R_{gen}$ usando \textit{Non-Dominated Sorting} (ver Sección \ref{sec:paretobased}): NDS($R_{gen}$) \label{pasonds}
		\STATE Formar la población de padres para la siguiente generación, $P_{gen+1}$, seleccionando $N$ individuos de $R_{gen}$ con base en la jerarquización obtenida en el paso \ref{pasonds}. Si existen más soluciones con la misma jerarquía que la capacidad disponible en $P_{gen+1}$ proceder de la siguiente manera: iterativamente estimar la aptitud con respecto al hipervolumen de dicho conjunto de soluciones y eliminar la solución con el peor desempeño, repitiendo este proceso hasta que solo queden los $N-|P_{gen+1}|$ individuos necesarios.
		\STATE $gen \leftarrow gen + 1$
	\ENDWHILE
\end{algorithmic}
\caption{$\mathbf{HypE}$: Flujo de ejecución.}
\label{alg:hype}
\end{algorithm}


\subsubsection{$\mathbf{MSOPS}$}
\label{sec:msops}

En 2003, Hughes \cite{Hughes03b} propuso el \textit{Multiple Single Objective Pareto Sampling} ($\mathbf{MSOPS}$) como una alternativa para optimizar problemas con muchos objetivos. $\mathbf{MSOPS}$ es una técnica que realiza en paralelo múltiples optimizaciones convencionales basadas en vectores de pesos, lo que permite buscar simultáneamente en diferentes direcciones. $\mathbf{MSOPS}$ no fue propuesto como un MOEA, sino como un mecanismo de jerarquización de soluciones que puede ser incorporado en una variedad de ellos. Este mecanismo consiste en utilizar $T$ vectores de pesos y evaluar las soluciones para cada uno de ellos con alguna técnica de agregación. Una matriz $S$, con $N$ renglones y $T$ columnas, almacenará el desempeño de cada uno de los $N$ individuos con respecto a los $T$ vectores de pesos. Posteriormente, cada columna de $S$ se jerarquiza de un modo tal que el individuo con el mejor desempeño tendrá jerarquía 1, mientras que la peor solución tendrá jerarquía $N$. La jerarquización resultante de las diferentes columnas será almacenada en una matriz $R$. Los renglones de $R$ son ahora ordenados ascendentemente, de manera que en la primera columna se encontrará la mejor jerarquía de cada individuo. Finalmente, a partir de la matriz $R$ es posible comparar y jerarquizar las soluciones. El Algoritmo \ref{alg:msops} ilustra el procedimiento que puede utilizarse para comparar dos soluciones $\mathbf{X}_{i}$ y $\mathbf{X}_{j}$ utilizando la matriz $R$.

\begin{algorithm}[H]
\begin{algorithmic}
	\REQUIRE \textbf{function} comparación\_MSOPS($\mathbf{X}_{i}$, $\mathbf{X}_{j}$)
	\FOR{$t=1$ to $T$}
		\IF{$R[\mathbf{X}_{i}][t] < R[\mathbf{X}_{j}][t]$} \RETURN $\mathbf{X}_{i}$ 
		\ELSIF{$R[\mathbf{X}_{j}][t] < R[\mathbf{X}_{i}][t]$} \RETURN $\mathbf{X}_{j}$ \ENDIF
	\ENDFOR
	\RETURN \textit{iguales}
	\ENSURE \textbf{function}
\end{algorithmic}
\caption{$\mathbf{MSOPS}$: Comparación de dos soluciones utilizando la matriz $R$.}
\label{alg:msops}
\end{algorithm}

En \cite{Hughes03b} se propone utilizar Min-Max con pesos (\textit{Weighted Min-Max}) en combinación con un enfoque al que Hughes nombró \textit{Vector Angle Distance Scaling} (VADS): \textit{optimización dual} (\textit{dual optimization}). De tal forma se utilizó $\mathbf{MSOPS}$ para este trabajo. Utilizar estas dos técnicas en conjunción implica que las matrices $S$ y $R$ tendrán $2T$ columnas, una para cada vector de pesos con cada uno de los dos enfoques. De acuerdo con Hughes \cite{Hughes03b}, el número y calidad de los vectores de pesos son factores que determinarán la capacidad del algoritmo para aproximar la superficie compromiso. Para este trabajo se utilizaron 100 vectores de pesos generados con una herramienta desarrollada por Hughes disponible para uso académico en \cite{hughescodes}. Sin embargo, por limitantes de tiempo y por conveniencia se utilizó la versión de $\mathbf{MSOPS}$ implementada y disponible en el marco de trabajo PISA \cite{Bleuler03}.



\subsection{Resultados}
\label{sec:resultadosalgorithms}

Los resultados de esta estapa de experimentación se presentan mediante diagramas de cajas (boxplots), puesto que son gráficas que muestran simultáneamente diferentes medidas descriptivas; v.g., valores que describen ciertos aspectos importantes de un conjunto de datos (en nuestro caso el conjunto de datos corresponde a las diferentes repeticiones de cada experimento). La interpretación de los diagramas utilizados se muestra en la figura \ref{fig:boxexplanation}. 
\begin{figure}[htp]
\centering
\shadowbox{
\includegraphics[width=0.6\textwidth]{boxplot_explanation.pdf}
}
\caption{Interpretación de los diagramas de cajas (boxplots).} \label{fig:boxexplanation}
\end{figure}
Aunque todos los datos mostrados en estas gráficas son importantes, de particular interés son los límites de las cajas y la barra dentro de éstas, siendo los principales puntos de referencia para comparaciones. Los límites inferior y superior de las cajas representan el primer y tercer cuartil respectivamente. La longitud de la caja es, por lo tanto, el rango intercuartil, de manera que cuanto más grande sea la caja, mayor será la dispersión de los datos. De este modo, la caja contendrá el 50\% central de los valores de un grupo. La barra horizontal que aparece dentro de la caja identifica la mediana del conjunto de valores (segundo cuartil), siendo una medida de tendencia central que, a diferencia de la media, no es tan susceptible a valores anómalos (atípicos). 


\subsubsection{Convergencia}
\label{sec:convergenciaalgorithms}
 

El propósito de este experimento es investigar la habilidad de los diferentes algoritmos estudiados para converger en espacios de objetivos con alta dimensionalidad. Los resultados obtenidos por los diferentes enfoques fueron evaluados utilizando la métrica de convergencia descrita en la Sección \ref{sec:convergencemetric}.

Las figuras \ref{fig:convergencealgorithmsd1} a \ref{fig:convergencealgorithmsd6} muestran los resultados obtenidos para los problemas DTLZ1 a DTLZ6 respectivamente. Los datos graficados corresponden a 31 corridas independientes para cada configuración del experimento. La métrica de convergencia es un criterio de minimización, por lo que mientras mas bajo sea el valor para la métrica (menor altura de las cajas) mejor será la convergencia lograda por un algoritmo. 

De manera general, está claro que nuestros algoritmos $\mathbf{CEGA^*}$ y $\mathbf{MDFA^*}$ mostraron el mejor desempeño para este experimento, puesto que en todas las instancias de los diferentes problemas de prueba alcanzaron los niveles más bajos para la métrica de convergencia, superando significativamente a los 4 enfoques del estado del arte elegidos para comparación. Comparando específicamente nuestros enfoques, consideramos que en términos de convergencia $\mathbf{CEGA^*}$ es superior a $\mathbf{MDFA^*}$, ya que en la mayoría de los casos obtuvo mejores resultados. Únicamente en los problemas DTLZ3 y DTLZ6 (figuras \ref{fig:convergencealgorithmsd3} y \ref{fig:convergencealgorithmsd6}, respectivamente) las diferencias no son tan significativas como para considerar que alguno de estos dos enfoques es superior a otro.

Al analizar el comportamiento de nuestros enfoques en los diferentes casos de prueba se puede observar que el desempeño de $\mathbf{CEGA^*}$ mejora al incrementarse la cantidad de objetivos. Este comportamiento se presenta en el caso de los problemas DTLZ1, DTLZ2, DTLZ4 y DTLZ5. Para DTLZ3 sólo se cumple en las tres instancias más pequeñas, mientras que para el problema DTLZ6 el desempeño de este enfoque es similar en todas las instancias. Este comportamiento de $\mathbf{CEGA^*}$ nos  permite establecer tendencias en su escalabilidad con respecto al número de objetivos y su robustez ante diferentes problemas de prueba. En términos de convergencia es posible argumentar que, al menos para los problemas de prueba utilizados, incrementar la cantidad de objetivos no tuvo efectos negativos sobre $\mathbf{CEGA^*}$. Por otro lado, en la mayoría de los casos el desempeño de $\mathbf{MDFA^*}$ empeora ligeramente de forma gradual al incrementarse la cantidad de objetivos, lo que nos indica que aunque su habilidad de convergencia no es mala, es un enfoque más susceptible a este factor al compararse con $\mathbf{CEGA^*}$.

$\mathbf{NSGA}$-$\mathbf{II}$ fue inferior a $\mathbf{DMO}$ en la mayoría de las instancias de este experimento. Estos resultados confirman que el uso de mecanismos para promover diversidad puede resultar nocivo  en escenarios con muchos objetivos. Sin embargo, la mejora de $\mathbf{DMO}$ sobre $\mathbf{NSGA}$-$\mathbf{II}$ no es tan significativa como para alcanzar buenos niveles de convergencia, ya que sigue siendo un método que usa como criterio de convergencia la relación de dominancia de Pareto que, como ya se ha discutido previamente, pierde sus efectos de discriminación al incrementarse la cantidad de objetivos provocando que el proceso de búsqueda sea guiado prácticamente de manera aleatoria. Por otra parte, de los cuatro algoritmos del estado del arte elegidos para la comparación, $\mathbf{MSOPS}$ fue el enfoque que mostró una mejor convergencia en la mayoría de los casos.

El rango de los resultados mostrados en cada figura confirma que los problemas DTLZ1, DTLZ3 y DTLZ6 involucran mayores dificultades de convergencia que el resto de los casos de prueba, tal como la definición de estos problemas lo sugiere (ver Sección \ref{sec:dtlz}). Para estos tres problemas la diferencia entre la convergencia lograda por nuestros enfoques y los algoritmos de la literatura es notablemente significativa, de tal forma se puede destacar la robustez y habilidad de convergencia de $\mathbf{CEGA^*}$ y $\mathbf{MDFA^*}$. 



\begin{figure}[h]
\centering
% \vspace{-0.5cm}
\caption{Métrica de convergencia. Problema DTLZ1.} \label{fig:convergencealgorithmsd1}
\includegraphics[width=\textwidth]{boxplot_dtlz1.pdf}
\vspace{-1cm}
\end{figure}


\begin{figure}[h]
\centering
\caption{Métrica de convergencia. Problema DTLZ2.} \label{fig:convergencealgorithmsd2}
\includegraphics[width=\textwidth]{boxplot_dtlz2.pdf}
\end{figure}


\begin{figure}[h]
\centering
\caption{Métrica de convergencia. Problema DTLZ3.} \label{fig:convergencealgorithmsd3}
\includegraphics[width=\textwidth]{boxplot_dtlz3.pdf}
\end{figure}


\begin{figure}[h]
\centering
\caption{Métrica de convergencia. Problema DTLZ4.} \label{fig:convergencealgorithmsd4}
\includegraphics[width=\textwidth]{boxplot_dtlz4.pdf}
\end{figure}

\clearpage

\begin{figure}[h]
\centering
\caption{Métrica de convergencia. Problema DTLZ5.} \label{fig:convergencealgorithmsd5}
\includegraphics[width=\textwidth]{boxplot_dtlz5.pdf}
\end{figure}

%\clearpage
\begin{figure}[h]
\centering
\caption{Métrica de convergencia. Problema DTLZ6.} \label{fig:convergencealgorithmsd6}
\includegraphics[width=\textwidth]{boxplot_dtlz6.pdf}
\end{figure}



\subsubsection{Distancia generacional invertida}
\label{sec:igdalgorithms}
 
% Aunque la convergencia debe ser prioridad en cualquier tarea de optimización, al optimizar múltiples objetivos un aspecto importante es lograr un conjunto diverso de soluciones que aproxime de manera representativa la superficie compromiso para determinado problema. 

La distancia generacional invertida (DGI) es una métrica que permite evaluar simultáneamente la habilidad de convergencia de los MOEAs y la capacidad que estos tienen para encontrar un conjunto diverso de soluciones. DGI es un criterio de minimización, de manera que cuánto más bajo sea el valor para esta métrica, mejor será el desempeño del MOEA evaluado. Para mayores detalles de esta métrica referirse a la Sección \ref{sec:igdmetric}.

Las figuras \ref{fig:igdalgorithmsd1} a \ref{fig:igdalgorithmsd6} muestran los resultados de este experimento para los problemas DTLZ1 a DTLZ6, respectivamente. Los datos en estas figuras corresponden a 31 ejecuciones independientes para cada instancia del experimento, y la interpretación de estas figuras es aquella descrita al inicio de la Sección \ref{sec:algorithmsexperimentation} mediante la figura \ref{fig:boxexplanation}.


Para este experimento podemos distinguir principalmente dos conjuntos de problemas en los que pueden agruparse los comportamientos observados. Por una parte están los problemas DTLZ1, DTLZ3 y DTLZ6, en los que nuestros algoritmos $\mathbf{CEGA^*}$ y $\mathbf{MDFA^*}$ mostraron superioridad para sus diferentes instancias. En el caso del problema DTLZ1 los resultados de $\mathbf{MSOPS}$ son muy cercanos a los de nuestros enfoques. Sin embargo, la amplitud de su correspondiente caja y las ejecuciones atípicas para las diferentes instancias de este problema son factores que nos indican que presenta un desempeño más inconsistente. Contrastando estas observaciones con los resultados de la Sección \ref{sec:convergenciaalgorithms} es posible remarcar que, aunque $\mathbf{MSOPS}$ no alcanza los mejores niveles de convergencia, logra obtener un conjunto de soluciones suficientemente distribuido como para mostrar resultados competitivos en este experimento. Por otro lado, en el caso de los problemas DTLZ3 y DTLZ6 la superioridad de nuestros enfoques fue más evidente. Estos tres problemas, de acuerdo con su definición (ver Sección \ref{sec:dtlz}) y con los resultados de la Sección \ref{sec:convergenciaalgorithms}, son los que involucran mayores dificultades de convergencia.


El segundo conjunto de observaciones corresponde a los problemas DTLZ2, DTLZ4 y DTLZ5, en los que se presenta un comportamiento parecido para los distintos algoritmos. En general podemos considerar que $\mathbf{HypE}$, $\mathbf{MSOPS}$, y nuestras propuestas $\mathbf{CEGA^*}$ y $\mathbf{MDFA^*}$ son los cuatro algoritmos que mejor se desempeñaron para estos problemas de prueba.  En el caso del problema DTLZ2,  el peor desempeño para la instancia más pequeña ($M=5$) se le atribuye a nuestro algoritmo $\mathbf{MDFA^*}$, pero mejoró gradualmente al incrementarse el número de objetivos. Por el contrario, $\mathbf{MSOPS}$ comenzó mostrando el mejor desempeño, pero esta diferencia se redujo para instancias más grandes del problema. A partir de $M=15$ los algoritmos $\mathbf{HypE}$, $\mathbf{MSOPS}$, $\mathbf{CEGA^*}$ y $\mathbf{MDFA^*}$ se comportaron de manera similar obteniendo los mejores resultados. Para el problema DTLZ4, en la instancia más pequeña $\mathbf{CEGA^*}$ y $\mathbf{MDFA^*}$ obtuvieron los peores resultados, mientras que $\mathbf{MSOPS}$ nuevamente mostró el mejor desempeño. Sin embargo, con el incremento en las dimensiones del problema estas diferencias se aminoraron y a partir de $M=15$ la diferencia entre $\mathbf{HypE}$, $\mathbf{MSOPS}$, $\mathbf{CEGA^*}$ y $\mathbf{MDFA^*}$ fueron mínimas. Finalmente, en todas las instancias del problema DTLZ5 los algoritmos $\mathbf{HypE}$, $\mathbf{MSOPS}$ y $\mathbf{CEGA^*}$ mostraron el mejor desempeño, mientras que nuevamente $\mathbf{MDFA^*}$ comenzó con los peores resultados pero para instancias más grandes se equiparó con este grupo de algoritmos.

En nuestra opinión, para este segundo conjunto de casos de prueba las diferencias entre el desempeño de los seis algoritmos evaluados no son tan significativas como para establecer aseveraciones fuertes sobre la superioridad de alguno de ellos. Sin embargo, es preciso señalar que en las diferentes instancias de estos tres problemas, nuestros enfoques $\mathbf{CEGA^*}$ y $\mathbf{MDFA^*}$ fueron igualados o superados por algunos de los algoritmos del estado del arte. Estos resultados nos indican que $\mathbf{CEGA^*}$ y $\mathbf{MDFA^*}$ son inferiores en cuanto a la habilidad para mantener un conjunto diversificado de soluciones. Aunque los diferentes algoritmos del estado del arte no alcanzaron los mejores niveles de convergencia, su buena capacidad para mantener diversidad en la población y los paisajes de aptitud (notablemente menos complicados) de estos tres problemas de prueba son factores que les permitieron mostrar resultados competitivos para este experimento.

\begin{figure}[htp]
\centering
\caption{Métrica DGI. Problema DTLZ1.} \label{fig:igdalgorithmsd1}
\includegraphics[width=\textwidth]{boxplot_igd_dtlz1.pdf}
\end{figure}


\begin{figure}[htp]
\centering
\caption{Métrica DGI. Problema DTLZ2.} \label{fig:igdalgorithmsd2}
\includegraphics[width=\textwidth]{boxplot_igd_dtlz2.pdf}
\end{figure}


\begin{figure}[htp]
\centering
\caption{Métrica DGI. Problema DTLZ3.} \label{fig:igdalgorithmsd3}
\includegraphics[width=\textwidth]{boxplot_igd_dtlz3.pdf}
\end{figure}



\begin{figure}[htp]
\centering
\caption{Métrica DGI. Problema DTLZ4.} \label{fig:igdalgorithmsd4}
\includegraphics[width=\textwidth]{boxplot_igd_dtlz4.pdf}
\end{figure}


\begin{figure}[htp]
\centering
\caption{Métrica DGI. Problema DTLZ5.} \label{fig:igdalgorithmsd5}
\includegraphics[width=\textwidth]{boxplot_igd_dtlz5.pdf}
\end{figure}

\clearpage
\begin{figure}[htp]
\centering
\caption{Métrica DGI. Problema DTLZ6.} \label{fig:igdalgorithmsd6}
\includegraphics[width=\textwidth]{boxplot_igd_dtlz6.pdf}
\end{figure}

%\clearpage

\section{Conclusiones del capítulo}
\label{sec:igdalgorithms}


En este capítulo se presentaron dos nuevos MOEAs: $\mathbf{CEGA}^*$ y $\mathbf{MDFA}^*$. Estos enfoques se propusieron como  alternativas capaces de converger en espacios de objetivos con alta dimensionalidad, y que al mismo tiempo incorporen mecanismos que promuevan la existencia de diversidad en la población sin afectar negativamente la convergencia.

En este capítulo también se presentaron los resultados de un estudio comparativo donde se evaluaron los dos nuevos MOEAs y cuatro enfoques representativos de la literatura. Para estos experimentos se consideró un conjunto de seis problemas de prueba escalables con instancias que involucran $M=\{5,10,15,20,30,50\}$ objetivos. 

Los resultados de este estudio indican que en términos de convergencia los dos enfoques propuestos son significativamente superiores a los cuatro MOEAs tomados de la literatura. El éxito de nuestros enfoques en términos de convergencia es principalmente el resultado de las estrategias de discriminación adoptadas. Comparando específicamente nuestras propuestas,  $\mathbf{CEGA}^*$ mostró un mejor desempeño que $\mathbf{MDFA}^*$ en la mayoría de los casos de prueba. Una observación importante acerca de $\mathbf{CEGA}^*$ es que el incremento en la cantidad de objetivos no tiene efectos negativos sobre este enfoque, ya incluso sus resultados mejoraron cuando se realizó un incremento en la dimensión de la mayoría de los problemas de prueba considerados.

Por otra parte, aún cuando nuestras propuestas demostraron ser superiores en términos de convergencia, los resultados indican que los enfoques del estado del arte proveen una mejor preservación de diversidad. Aunque los enfoques de la literatura no lograron la mejor convergencia, la diversidad de su conjunto aproximación fue suficiente para lograr resultados competitivos de la métrica utilizada. A pesar de que nuestros enfoques incorporan mecanismos para promover la diversidad, es notorio que no son capaces de converger de una manera suficientemente distribuida.

Estos resultados hacen clara la necesidad de desarrollar mecanismos más efectivos para preservación de diversidad y que puedan trabajar en conjunto con una jerarquización estricta de las soluciones, de tal manera que se logre un balance adecuado entre los requerimientos de convergencia y diversidad.


